Paper 2021/089

Fuzzy Message Detection

Gabrielle Beck, Julia Len, Ian Miers, and Matthew Green

Abstract

Many privacy-preserving protocols employ a primitive that allows a sender to "flag" a message to a recipient's public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate $p$. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACM CCS
DOI
10.1145/3460120.3484545
Keywords
privacyencryptioncryptocurrency
Contact author(s)
matthewdgreen @ gmail com
becgabri @ cs jhu edu
History
2021-11-22: last of 4 revisions
2021-01-27: received
See all versions
Short URL
https://ia.cr/2021/089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/089,
      author = {Gabrielle Beck and Julia Len and Ian Miers and Matthew Green},
      title = {Fuzzy Message Detection},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/089},
      year = {2021},
      doi = {10.1145/3460120.3484545},
      url = {https://eprint.iacr.org/2021/089}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.